


#include <stdio.h>

#include <assert.h>
#define SUB 5

void Print(int* a, int n)
{
    printf("arr1[]= ");
    for (int i = 0; i < n; ++i)
    {
        printf("%3d ", a[i]);
    }
    putchar('\n');
}

void ShellSort(int* a, int n)
{
    assert(a);

    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;

        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];

            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }

    }
}

int* relativeSortArray1(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
{
    *returnSize = arr1Size;

    int cnt[1001] = { 0 };
    for (int i = 0; i < arr1Size; ++i)
    {
        cnt[arr1[i]]++;
    }

    if (arr1Size == arr2Size)
    {
        int j = 0;
        for (int i = 0; i < arr2Size; ++i)
        {
            while (cnt[arr2[i]]--)
            {
                arr1[j++] = arr2[i];
            }
        }

        return arr1;
    }

    int sub[SUB];
    int cnt_sub = 0;
    for (int i = 0; i < arr1Size; ++i)
    {
        int flag = 0;
        for (int j = 0; j < arr2Size; ++j)
        {
            if (arr1[i] == arr2[j])
                flag = 1;
        }

        if (0 == flag)
            sub[cnt_sub++] = arr1[i];
    }

    int j = 0;
    for (int i = 0; i < arr2Size; ++i)
    {
        while (cnt[arr2[i]]--)
        {
            arr1[j++] = arr2[i];
        }
    }

    ShellSort(sub, cnt_sub);
    for (int i = 0; i < cnt_sub; ++i)
    {
        arr1[j++] = sub[i];
    }

    return arr1;
}

//int* relativeSortArray2(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
//{
//    *returnSize = arr1Size;
//
//    int cnt[1001] = { 0 };
//    for (int i = 0; i < arr1Size; ++i)
//    {
//        cnt[arr1[i]]++;
//    }
//
//    for (int i = 0, j = 0; i < arr2Size; ++i)
//    {
//        while (cnt[arr2[i]]--)
//        {
//            arr1[j++] = arr2[i];
//        }
//    }
//
//    if (arr1Size != arr2Size)
//    {
//        int k = arr1Size - 1;
//        for (int i = 0; i < 1001; ++i)
//        {
//            if (cnt[i])
//            {
//                int flag = 0;
//                for (int j = 0; j < arr2Size; ++j)
//                {
//                    if (i == arr2[j])
//                        flag = 1;
//                }
//
//                if (0 == flag)
//                {
//                    while (cnt[i]--)
//                    {
//                        arr1[k--] = i;
//                    }
//                }
//            }
//
//        }
//
//        if (k < arr1Size-2)
//            ShellSort(arr1 + k + 1, arr1Size - (k + 1));
//    }
//
//    return arr1;
//}

int* relativeSortArray3(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
{
    *returnSize = arr1Size;

    int cnt[1001] = { 0 };
    for (int i = 0; i < arr1Size; ++i)
    {
        cnt[arr1[i]]++;
    }

    for (int i = 0, j = 0; i < arr2Size; ++i)
    {
        while (cnt[arr2[i]]--)
        {
            arr1[j++] = arr2[i];
        }
    }

    if (arr1Size != arr2Size)
    {
        int k = arr1Size - 1;
        for (int i = 0; i < 1001; ++i)
        {
            if (cnt[i] > 0)
            {
                while (cnt[i]--)
                {
                    arr1[k--] = i;
                }
            }
        }

        if (k < arr1Size - 2)
            ShellSort(arr1 + k + 1, arr1Size - (k + 1));
    }

    return arr1;
}
int main()
{
    /*int arr1[] = { 2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19 };
    int arr2[] = {2, 1, 4, 3, 9, 6 };*/
    /* int arr1[] = { 943, 790, 427, 722, 860, 550, 225, 846, 715, 320 };
     int arr2[] = {943,715,427,790,860,722,225,320,846,550 };*/
    int arr1[] = { 2, 21, 43, 38, 0, 42, 33, 7, 24, 13, 12, 27, 12, 24, 5, 23, 29, 48, 30, 31 };
    int arr2[] = {2, 42, 38, 0, 43, 21};
    int arr1Size = sizeof(arr1) / sizeof(arr1[0]);
    int arr2Size = sizeof(arr2) / sizeof(arr2[0]);
    int returnSize = 0;

    Print(arr1, arr1Size);
    relativeSortArray3(arr1, arr1Size, arr2, arr2Size, &returnSize);
    Print(arr1, arr1Size);

    return 0;
}